package practice;


import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Day26 {

    //滑动窗口的最大值
    //https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->{
            //大根堆
            return a[0] - b[0] >= 0 ? -1 : 1;
        });
        int right = 0;
        for(right = 0; right < k; right++) {
            queue.offer(new int[]{nums[right],right});
        }
        list.add(queue.peek()[0]);
        while(right < n) {
            queue.offer(new int[]{nums[right],right});
            while(queue.peek()[1] <= right-k) {
                //最大的元素没在范围内了
                queue.poll();
            }
            list.add(queue.peek()[0]);
            right++;
        }
        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
    //按升序排链表
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(cur);
        //合并
        ListNode newHead = new ListNode(0);
        ListNode tmp = newHead;
        while(left != null && right != null) {
            if(left.val <= right.val) {
                tmp.next = left;
                left = left.next;
            }else {
                tmp.next = right;
                right = right.next;
            }
            tmp = tmp.next;
        }
        tmp.next = (left == null) ? right : left;
        return newHead.next;
    }
}
